/**
 * @author ZhengDp
 * @Date 2023/4/30 11:04
 */
public class KMP {

    public static int kmp(String s,String p) {
        int[] next = getNext(p);
        int i =0,j=0;
        while(i<s.length() && j < p.length()) {
            if(j == -1 || s.charAt(i) == p.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if(j == p.length()) {
            return i-j;
        } else {
            return -1;
        }
    }


    private static int[] getNext(String p) {
        int len = p.length();
        int k = -1,j=0;
        int[] next = new int[len];
        while(j < len) {
            if(k == -1 || p.charAt(j) == p.charAt(k)) {
                // next[j] : 不包括j
                k++;
                j++;
                next[j] = k;
            } else {
                k = next[k];
            }
        }

        return next;
    }
}
